import java.io.*;
import java.util.*;
import java.util.regex.*;

public class Syntax {

    private static final String GRAMMER_PATH = "grammer.txt";
    private static final String LEX_FILE_PATH = "lexical.txt";
    private static final String SYNTAX_ANALYSIS_PATH = "syntax_analysis.txt";
    private static final String FIRST_FILE = "first.txt";
    private static final String FOLLOW_FILE = "follow.txt";
    private static final String TABLE_FILE = "table.txt";

    private Map<String, Integer> vnMap = new HashMap<>();
    private Map<String, Integer> vtMap = new HashMap<>();
    private List<List<List<String>>> productions = new ArrayList<>();
    private Map<String, Set<String>> first = new HashMap<>();
    private Map<String, Set<String>> follow = new HashMap<>();
    private List<String> inputChars = new ArrayList<>();
    private Deque<String> stack = new ArrayDeque<>();
    private Pair[][] table;
    private int vnCount = 0;
    private int vtCount = 0;
    private Set<String> visited = new HashSet<>();
    private Set<String> Vn = new HashSet<>();  // 非终结符集合
    private Set<String> Vt = new HashSet<>();  // 终结符集合
    private List<Token> tokens = new ArrayList<>();


    public static class Pair<K, V> {
        public K first;
        public V second;

        public Pair(K first, V second) {
            this.first = first;
            this.second = second;
        }

        @Override
        public String toString() {
            return "(" + first + "," + second + ")";
        }
    }

    public static class Token{
        public String token;
        public String type;
        public String detail;
    }

    public Syntax() {
        productions.add(new ArrayList<>()); // 添加占位，确保索引从1开始
    }

    public void classifySymbols() {
        try (BufferedReader reader = new BufferedReader(new FileReader(GRAMMER_PATH))) {
            String line;
            while ((line = reader.readLine()) != null) {
                line = line.trim();
                if (line.isEmpty()) continue;  // 跳过空行

                String[] parts = line.split("->");
                if (parts.length != 2) continue;  // 非法产生式，跳过

                String left = parts[0].trim();  // 左部非终结符
                String[] rightParts = parts[1].trim().split("\\|");  // 右部多个选项

                // 将左部非终结符添加到 Vn 集合中
                Vn.add(left);

                // 遍历右部每个选项
                for (String right : rightParts) {
                    String[] symbols = right.trim().split("\\s+");
                    for (String symbol : symbols) {
                        // 如果是非终结符，加入 Vn 集合
                        if (!Vn.contains(symbol)) {
                            Vt.add(symbol);  // 否则是终结符，加入 Vt 集合
                        }
                    }
                }
            }
            // 从终结符集合中移除所有非终结符
            for (String nonTerminal : Vn) {
                Vt.remove(nonTerminal);
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }


    public void parseGrammar() {
        try (BufferedReader reader = new BufferedReader(new FileReader(GRAMMER_PATH))) {
            String line;
            while ((line = reader.readLine()) != null) {
                line = line.trim();
                if (line.isEmpty()) continue; // 跳过空行

                String[] parts = line.split("->");
                if (parts.length != 2) continue; // 非法产生式，跳过

                String left = parts[0].trim(); // 左部非终结符
                String[] rightParts = parts[1].trim().split("\\|"); // 右部多个选项
                // 添加左部符号为非终结符
                if (!vnMap.containsKey(left)) {
                    vnMap.put(left, ++vnCount);
                    productions.add(new ArrayList<>()); // 对应的非终结符创建一个新的列表
                }

                // 获取左部非终结符的 ID
                int leftId = vnMap.get(left) ;

                // 遍历右部每个选项，形成产生式
                for (String right : rightParts) {
                    String[] symbols = right.trim().split("\\s+");
                    List<String> production = new ArrayList<>();
                    for (String symbol : symbols) {
                        production.add(symbol);
                        // 如果符号是非终结符且未记录，加入 vnMap
                        if (Vt.contains(symbol)&& !vtMap.containsKey(symbol)) {
                            vtMap.put(symbol, ++vtCount); // 这里假设只有标识符会是终结符
                        }else if (!vnMap.containsKey(symbol)&& !Vt.contains(symbol)) {
                            vnMap.put(symbol, ++vnCount);
                            productions.add(new ArrayList<>());
                        }
                    }
                    productions.get(leftId).add(production);
                }
            }

            // 从终结符集合中移除所有非终结符
            for (String nonTerminal : vnMap.keySet()) {
                vtMap.remove(nonTerminal);
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }


    public void computeFirst() {
        // 初始化终结符的 FIRST 集，终结符的 FIRST 集为其自身
        for (String terminal : vtMap.keySet()) {
            first.put(terminal, new HashSet<>(Collections.singletonList(terminal)));
        }

        // 初始化非终结符的 FIRST 集为空
        for (String nonTerminal : vnMap.keySet()) {
            first.putIfAbsent(nonTerminal, new HashSet<>());
        }

        boolean updated;
        do {
            updated = false; // 每次迭代开始时将 updated 置为 false
            // 遍历每个非终结符
            for (int i = 1; i < productions.size(); i++) {
                String head = getVnById(i); // 获取非终结符
                for (List<String> production : productions.get(i)) { // 遍历每个产生式
                    Set<String> currentFirst = first.get(head);
                    int beforeSize = currentFirst.size(); // 记录计算前的大小

                    boolean allHaveEpsilon = true; // 判断是否所有符号能推出空符号

                    // 遍历右部的每个符号
                    for (String symbol : production) {
                        computeFirstForSymbol(symbol); // 递归计算符号的 FIRST 集

                        Set<String> symbolFirst = first.get(symbol);
                        if (symbolFirst != null) {
                            currentFirst.addAll(symbolFirst); // 将符号的 FIRST 集加入到当前非终结符的 FIRST 集
                            currentFirst.remove("$"); // 移除空符号

                            // 如果当前符号的 FIRST 集不包含空符号，停止处理后续符号
                            if (!symbolFirst.contains("$")) {
                                allHaveEpsilon = false;
                                break;
                            }
                        }
                    }

                    // 如果右部所有符号都能推导出空符号，则将空符号加入当前非终结符的 FIRST 集
                    if (allHaveEpsilon) { // 只有在不包含$时才加入
                        currentFirst.add("$");
                    }

                    // 如果当前 FIRST 集发生变化，则继续迭代
                    if (currentFirst.size() > beforeSize && !allHaveEpsilon) {
                        updated = true;
                    }
                }
            }
        } while (updated); // 只有在 FIRST 集发生变化时才继续迭代
    }


    // 递归计算单个符号的 FIRST 集
    private void computeFirstForSymbol(String symbol) {
        // 如果是终结符，直接返回
        if (vtMap.containsKey(symbol)) return;

        // 如果该符号已经计算过，说明已经计算过了，直接返回
        if (visited.contains(symbol)) return;

        // 标记该符号正在被计算
        visited.add(symbol);

        // 如果是非终结符且没有计算过，递归计算其 FIRST 集
        if (vnMap.containsKey(symbol)) {
            int id = vnMap.get(symbol);
            for (List<String> production : productions.get(id)) {
                boolean allHaveEpsilon = true;
                for (String s : production) {
                    computeFirstForSymbol(s); // 递归计算
                    Set<String> symbolFirst = first.get(s);
                    if (symbolFirst != null) {
                        first.get(symbol).addAll(symbolFirst);
                        first.get(symbol).remove("$"); // 移除空符号
                        if (!symbolFirst.contains("$")) {
                            allHaveEpsilon = false;
                            break;
                        }
                    }
                }
                // 如果右部所有符号都能推出空符号，则将空符号加到该非终结符的 FIRST 集
                if (allHaveEpsilon) {
                    first.get(symbol).add("$");
                }
            }
        }

        // 标记该符号计算结束，允许其他符号继续计算
        visited.remove(symbol);
    }


    public void computeFollow() {
        // 初始化 FOLLOW 集
        for (String nonTerminal : vnMap.keySet()) {
            follow.putIfAbsent(nonTerminal, new HashSet<>());
        }
        follow.get(getVnById(1)).add("#"); // 添加起始符号的 FOLLOW 集

        boolean updated;
        do {
            updated = false;
            for (int i = 1; i < productions.size(); i++) {
                String head = getVnById(i);
                for (List<String> production : productions.get(i)) {
                    Set<String> trailer = new HashSet<>(follow.get(head));
                    for (int j = production.size() - 1; j >= 0; j--) {
                        String symbol = production.get(j);
                        if (vnMap.containsKey(symbol)) { // 如果是非终结符
                            Set<String> followSet = follow.computeIfAbsent(symbol, k -> new HashSet<>());
                            int beforeSize = followSet.size();
                            followSet.addAll(trailer);
                            if (followSet.size() > beforeSize) updated = true;

                            if (first.get(symbol).contains("$")) {
                                trailer.addAll(first.get(symbol));
                                trailer.remove("$");
                            } else {
                                trailer = new HashSet<>(first.get(symbol));
                            }
                        } else {
                            trailer = new HashSet<>(first.get(symbol)); // 更新 trailer 为终结符的 FIRST
                        }
                    }
                }
            }
        } while (updated);
    }


    public void constructTable() {
        // 初始化预测分析表
        table = new Pair[vnCount + 2][vtCount + 2];

        // 初始化表格为默认值（0，-1），表示没有产生式
        for (int i = 1; i <= vnCount; i++) {
            for (int j = 1; j <= vtCount; j++) {
                table[i][j] = new Pair<>(0, -1); // 默认值表示没有规则
            }
        }

        // 遍历每个非终结符
        for (int i = 1; i <= vnCount; i++) {
            String head = getVnById(i);

            // 遍历每个产生式
            for (int j = 0; j < productions.get(i).size(); j++) {
                List<String> production = productions.get(i).get(j);

                // 计算当前产生式的 FIRST 集
                Set<String> firstSet = computeFirstForProduction(production);


                // 如果 FIRST 集不包含空符号，将相应的产生式加入预测分析表
                for (String terminal : firstSet) {
                    if (!terminal.equals("$")) {
                        int vnIndex = vnMap.get(head);
                        int vtIndex = vtMap.get(terminal);
                        table[vnIndex][vtIndex] = new Pair<>(i, j); // 填入产生式编号和产生式右侧的索引
                    }
                }

                // 如果 FIRST 集包含 $，则需要将 FOLLOW 集中的符号加入
                if (firstSet.contains("$")) {
                    Set<String> followSet = follow.get(head);

                    if (followSet != null) {
                        for (String terminal : followSet) {
                            int vnIndex = vnMap.get(head);
                            int vtIndex = vtMap.getOrDefault(terminal, vtCount+1); // # 符号可能是 vtCount 索引
                            table[vnIndex][vtIndex] = new Pair<>(i, j); // 填入产生式编号和产生式右侧的索引
                        }
                    }
                }
            }
        }
    }

    private Set<String> computeFirstForProduction(List<String> production) {
        Set<String> result = new HashSet<>();
        for (String symbol : production) {
            Set<String> symbolFirst = first.get(symbol);
            if (symbolFirst != null) {
                result.addAll(symbolFirst);
                if (!symbolFirst.contains("$")) break; // 如果不包含空符号，停止
            }
        }
        return result;
    }




    public void parseInput(String tokenFilePath) {
        tokens.clear();
        try (BufferedReader reader = new BufferedReader(new FileReader(tokenFilePath))) {
            String line;
            while ((line = reader.readLine()) != null) {
                line = line.trim();
                if (line.isEmpty()) continue; // 跳过空行

                // 分隔行的 token 和 type
                String[] parts = line.split("\t");
                if (parts.length != 2) {
                    System.err.println("Invalid line format: " + line);
                    continue;
                }

                String token = parts[0]; // 词法单元
                String typeDetail = parts[1]; // 类型和详情（如 <KW,1>）

                // 使用正则表达式解析 type 和 detail
                Pattern pattern = Pattern.compile("<(\\w+),(\\w+)>");
                Matcher matcher = pattern.matcher(typeDetail);
                if (!matcher.matches()) {
                    System.err.println("Invalid token format: " + typeDetail);
                    continue;
                }

                String type = matcher.group(1); // 提取类型
                String detail = matcher.group(2); // 提取详情

                // 创建 Token 对象并添加到 tokens 列表
                Token tokenObj = new Token();
                tokenObj.token = token;
                tokenObj.type = type;
                tokenObj.detail = detail; // 将 detail 直接存为字符串
                tokens.add(tokenObj);
            }

            // 添加结束符号 #
            Token endToken = new Token();
            endToken.token = "#";
            endToken.type = "EOF";
            endToken.detail = null; // EOF 没有具体值
            tokens.add(endToken);

        } catch (IOException e) {
            e.printStackTrace();
        }
    }



    public boolean analyze(String syntaxAnalysisFilePath) {
        stack.clear();
        stack.push("#");
        stack.push(getVnById(1));

        Iterator<Token> inputIterator = tokens.iterator();
        Token currentInput = inputIterator.next();
        int index=0;

        try (PrintWriter writer = new PrintWriter(new FileWriter(syntaxAnalysisFilePath))) {
            while (!stack.isEmpty()) {
                String top = stack.pop();
                if (currentInput.token.equals("||")){
                    currentInput.token = "^^";
                }
                if (vtMap.containsKey(top) || top.equals("#")) {
                    if (top.equals(currentInput.token)||top.equals(currentInput.type)) {
                        if (top.equals("#")) {
                            writer.printf(++index+"\t"+top+"#"+top+"\t"+"accept");
                            return true;
                        }
                        if(currentInput.token.equals("^^")){
                            currentInput.token = "||";
                            top="||";
                        }
                        writer.println(++index+"\t"+top+"#"+currentInput.token+"\t"+"move");
                        currentInput = inputIterator.next();
                    } else {
                        writer.println(++index+"\t"+top+"#"+currentInput.token+"\t"+"error");
                        return false;
                    }
                } else {
                    int vnIndex = vnMap.get(top);
                    int vtIndex;
                    if (vtMap.containsKey(currentInput.token)) {
                        vtIndex = vtMap.get(currentInput.token);
                    }else if (vtMap.containsKey(currentInput.type)) {
                        vtIndex = vtMap.get(currentInput.type);
                    }else {
                        vtIndex = vtCount + 1;
                    }
                    Pair<Integer, Integer> action = table[vnIndex][vtIndex];

                    if (action == null || action.second == -1) {
                        writer.printf("Error: no rule for %s on input %s%n", top, currentInput.token);
                        return false;
                    }
                    if(currentInput.token.equals("^^")){
                        currentInput.token = "||";
                    }
                    writer.println(++index+"\t"+top+"#"+currentInput.token+"\t"+"reduction");
                    List<String> production = productions.get(action.first).get(action.second);
                    for (int i = production.size() - 1; i >= 0; i--) {
                        if (!production.get(i).equals("$")){
                            stack.push(production.get(i));
                        }
                    }
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
        return false;
    }



    private String getVnById(int id) {
        for (Map.Entry<String, Integer> entry : vnMap.entrySet()) {
            if (entry.getValue() == id) return entry.getKey();
        }
        return null;
    }

    public void printTableToFile() {
        try (PrintWriter writer = new PrintWriter(new FileWriter(TABLE_FILE))) {
            // 打印表头（终结符的列表）
            writer.print("\t\t\t");
            for (String terminal : vtMap.keySet()) {
                if (terminal.equals("^^")){
                    terminal = "||";
                }
                writer.print(terminal + "\t");
            }
            writer.print("#" + "\t");
            writer.println();
            int index=0;
            writer.print("\t\t\t");
            for (String terminal : vtMap.keySet()) {
                writer.print(++index + "\t\t");
            }
            writer.print(++index+ "\t");
            writer.println();

            // 打印每个非终结符的行
            for (int i = 1; i <= vnCount; i++) {
                writer.print(getVnById(i) + "\t\t"); // 打印非终结符

                // 打印该非终结符在各个终结符列上的动作
                for (String terminal : vtMap.keySet()) {
                    int vtIndex = vtMap.getOrDefault(terminal, vtCount + 1);
                    Pair<Integer, Integer> action = table[i][vtIndex];

                    // 如果没有规则，则打印 "-"
                    if (action != null && action.second != -1) {
                        writer.print(action+"\t");
                    } else {
                        writer.print("__,__\t");
                    }
                }
                Pair<Integer, Integer> action = table[i][vtCount+1];
                if (action != null && action.second != -1) {
                    writer.print(action+"\t");
                } else {
                    writer.print("__,__\t");
                }

                writer.println();
            }

        } catch (IOException e) {
            e.printStackTrace();
        }
    }


    public void syntax() {
        classifySymbols();
        parseGrammar();
        computeFirst();
        computeFollow();
        constructTable();
    }
    public void test(String fromFile, String toFile) {
        parseInput(fromFile);
        if (analyze(toFile)) {
            System.out.println("Syntax analysis completed successfully.");
        } else {
            System.out.println("Syntax analysis failed.");
        }
    }

    public void printFirstToFile() {
        try (PrintWriter writer = new PrintWriter(new FileWriter("first.txt"))) {
            // 排序 Vn
            List<String> sortedVn = new ArrayList<>(vnMap.keySet());
            sortedVn.sort(String.CASE_INSENSITIVE_ORDER);
            for (String nonTerminal : sortedVn) {
                Set<String> firstSet = first.get(nonTerminal);
                // 使用 TreeSet 排序 FIRST 集中的符号
                TreeSet<String> sortedFirstSet = new TreeSet<>(firstSet);
                writer.println(nonTerminal);
                writer.print(" -- ");
                for (String symbol : sortedFirstSet) {
                    writer.print("'" + symbol + "' ");
                }
                writer.println();
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public void printFollowToFile() {
        try (PrintWriter writer = new PrintWriter(new FileWriter("follow.txt"))) {
            // 排序 Vn
            List<String> sortedVn = new ArrayList<>(vnMap.keySet());
            sortedVn.sort(String.CASE_INSENSITIVE_ORDER);
            for (String nonTerminal : sortedVn) {
                Set<String> followSet = follow.get(nonTerminal);
                // 使用 TreeSet 排序 FOLLOW 集中的符号
                TreeSet<String> sortedFollowSet = new TreeSet<>(followSet);
                writer.println(nonTerminal);
                writer.print(" -- ");
                for (String symbol : sortedFollowSet) {
                    writer.print("'" + symbol + "' ");
                }
                writer.println();
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public void printDetail(){
        printFirstToFile();
        System.out.println("FIRST set has been written to first.txt.");

        printFollowToFile();
        System.out.println("FOLLOW set has been written to follow.txt.");

        printTableToFile();
        System.out.println("ANALYSIS set has been written to syntax_analysis.txt");
    }

    private static Syntax compileFront(String source) {
        String lexPath="./test/lex/33-3lex.tsv";
        String graPath="./test/gra/33-3gra.tsv";
        Util.setLexicalTxtPath(lexPath);

        Lexical lexical = new Lexical();//初始化
        Syntax syntax = new Syntax();
        syntax.syntax();

        lexical.lexicalAnalysis(source);
        syntax.test(lexPath,graPath);
        return syntax;
    }

    private static void testSample(){
        String sourceBase="./test/sample";
        String lexBase="./test/lex/sample";
        String graBase="./test/gra/sample";
        Lexical lexical = new Lexical();//初始化
        Syntax syntax = new Syntax();
        syntax.syntax();
        for (int i=1;i<=10;i++){
            String lexPath=lexBase+i+"lex.tsv";
            String graPath=graBase+i+"gra.tsv";
            String sourcePath=sourceBase+i+".sy";
            Util.setLexicalTxtPath(lexPath);
            lexical.lexicalAnalysis(sourcePath);
            syntax.test(lexPath,graPath);
        }
        System.out.println("测试样例已完成");
    }

    public static void main(String[] args) {
//        String source="./test/33-3.sy";
//        Syntax syntax = compileFront(source);
//        syntax.printDetail();
        testSample();
    }

}
